public class OrderedLinkedList<E> {

	private class KeyedNode<E> {

		/*
		 * Variables
		 */
		private E object; //Holds the objects value.
		private String key; //Holds the objects String key
		private KeyedNode<E> next; //Holds the objects next reference.

		/**
		 * Constructor that sets the objects String Key, E object (or value), and sets the next reference.
		 * 
		 * @param key Key for the object.
		 * @param object Object that the key stores.
		 * @param next Next KeyedNode<E> reference.
		 */
		public KeyedNode(String key, E object, KeyedNode<E> next) {        
			this.key = key;
			this.object = object;
			this.next = next;
		}

		/**
		 * Constructor that that sets the objects String key, E object, and sets the next reference to null.
		 * 
		 * @param key Key for the object.
		 * @param object Object that the key stores.
		 */
		public KeyedNode(String key, E object) {
			this(key, object, null);
		}

		/**
		 * Returns this nodes object value.
		 *
		 * @return Returns this nodes object value.
		 */
		public E getObject() {
			return this.object;
		}

		/**
		 * Returns this nodes String key.
		 * 
		 * @return Returns this nodes String key.
		 */
		public String getKey() {
			return this.key;
		}

		/**
		 * Returns the next reference of this KeyedNode.
		 * 
		 * @return  Returns the next reference of this KeyedNode.
		 */
		public KeyedNode<E> getNext() {
			return this.next;
		}

		/**
		 * Sets the next reference of this KeyedNode.
		 * 
		 * @param next Sets the next reference of this KeyedNode.
		 */
		public void setNext(KeyedNode<E> next) {
			this.next = next;
		}

		/**
		 * Returns the value of the two Strings that are compared against each other.
		 * If the parameter key is larger than the key being compared against, 1 is returned.
		 * If the parameter key is smaller than the key being compared against, -1 is returned.
		 * Else returns 0.
		 * 
		 * @param otherKey Key to compare against the objects key.
		 * @return 1 If the objects key is larger than the passed key.
		 * @return -1 If the objects key is smaller than the passed key.
		 * @return 0 If both key values are the same.
		 */
		public int checkKeyValue(String otherKey) {
			return this.key.compareToIgnoreCase(otherKey);
		}

	}

	/*
	 * Variables
	 */
	private int size; //Holds the size of this OrderedLinkedList.
	private KeyedNode<E> head; //Points to the node at the beginning of this OrderedLinkedList.

	/**
	 * Creates an empty OrderedLinkedList.
	 */
	public OrderedLinkedList() {
		this.head = null;
		this.size = 0;
	}

	/**
	 * Returns the number of elements in the linked list. 
	 *
	 * @return Returns the number of elements in the linked list. 
	 */
	public int size() {
		return this.size;
	}

	/**
	 * If the list does not already contain the given key, the key and value are added to the linked list, and add returns null. 
	 * Otherwise, the existing object with the given key is replaced with the new object (and the new key), and add returns the old (removed) object.
	 *
	 * @param key The objects String key to reference it.
	 * @param value The objects value to store with the String key.
	 * @return null The list did not contain the given key, therefore return null after adding the new object.
	 * @return E There was a prior object with the same key.  Replace old object with new one and returns the old object.
	 */
	public E add(String key, E value) {
		//Integer of what current is set to compared to the new key value.
		int currentComparedToNewKey = 0;

		//Empty OrderedLinkedList, add to the front.
		if(this.head == null) {
			this.head = new KeyedNode<E>(key, value, this.head);
			this.size++;
			return null;
		} else {
			//Get new value of comparison between current and the new key value.
			currentComparedToNewKey = this.head.checkKeyValue(key);

			if(currentComparedToNewKey > 0) {
				//Base case 1
				//The head key is larger than the new key.  Set new object to the head and head's next is set to the original head.
				KeyedNode<E> oldObject = this.head;
				this.head = new KeyedNode<E>(key, value, oldObject);
				this.size++;
				return null;
			} else if(currentComparedToNewKey == 0) {
				//Base case 2
				//The head key is the same value as the new key.  Replace head with the new object and return the old object.
				KeyedNode<E> oldObject = this.head;
				this.head = new KeyedNode<E>(key, value, head.getNext());
				return oldObject.getObject();
			} else {
				//Base case 3
				//Go through the linked list to insert/replace new object.
				KeyedNode<E> previous = this.head;
				KeyedNode<E> current = this.head;

				while(current != null) {
					//Value of comparison is updated every time.
					currentComparedToNewKey = current.checkKeyValue(key);

					if(currentComparedToNewKey < 0) {
						//If we're at the end of the list and the current key is still smaller than the new key, add new object at the end.
						if(current.getNext() == null) {
							current.setNext(new KeyedNode<E>(key, value, null));
							this.size++;
							return null;
						}
					} else if(currentComparedToNewKey == 0) {
						//Found the same key value.  Replace old object with new object then return old object.
						KeyedNode<E> oldObject = current;
						current = new KeyedNode<E>(key, value, current.getNext());
						previous.setNext(current);  //Set previous' next to the new object.
						return oldObject.getObject();
					} else {
						//currentComparedToNewKey == 1
						//New object will be inserted between previous and current. 
						previous.setNext(new KeyedNode<E>(key, value, current));
						this.size++;
						return null;
					}

					//Update values to go through the list.  Previous always behind current.
					previous = current;
					current = current.getNext();
				}
			}
		}
		return null; //Shouldn't really hit this case.
	}

	/**
	 * Returns the matching object if the corresponding key is in the ordered linked list, and null otherwise. 
	 *
	 * @param key Searches for an object by looking for its key.
	 * @return Returns the object if found, otherwise returns null.
	 */
	public E find(String key) {
		KeyedNode<E> current = this.head;

		while(current != null) {
			if(current.checkKeyValue(key) == 0) {
				//Found the key! Return the object.
				return current.getObject();
			}
			//Haven't found the key yet, keep going through the OrderedLinkedList.
			current = current.getNext();
		}

		return null;
	}

	/**
	 * Returns the object at the given position, as long as the index is valid. Otherwise, it returns null 
	 * (this is unlike the standard get, which throws an exception if the index is invalid). 
	 *
	 * @param position Searches for an object at the given position.
	 * @return Returns the object at the given position.
	 */
	public E get(int position) {

		if(this.size == 0 || position < 0 || position > this.size) {
			//Base case 1
			return null;
		}

		//Assuming OrderedLinkedList is 0 index based.
		KeyedNode<E> current = this.head;
		for(int i = 0; i < position; i++) {
			current = current.getNext();
		}

		return current.getObject();
	}

	/**
	 * Prints all the keys and their associated objects.
	 */
	public void print() {
		KeyedNode<E> current = this.head;

		for(int i = 0; i < this.size; i++) {
			System.out.println((i + 1) + ") Name: " + current.getKey() + "\tTelephone number: " 
					+ current.getObject());
			current = current.getNext();
		}
	}

}